home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / source / graphicgems4.lha / GemsIV / vert_norm / smooth.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  8.9 KB  |  295 lines
  1. /*
  2.  * ANSI C code from the article
  3.  * "Building Vertex Normals from an Unstructured Polygon List"
  4.  * by Andrew Glassner, glassner@parc.xerox.com
  5.  * in "Graphics Gems IV", Academic Press, 1994
  6.  */
  7.  
  8. /* smooth.c - Compute vertex normals for polygons.
  9.    Andrew S. Glassner / Xerox PARC
  10.  
  11.   The general idea is to 1) initialize the tables, 2) add polygons one by one,
  12.   3) optionally enable edge preservation, 4) optionally set the fuzz factor,
  13.   5) compute the normals, 6) do something with the new normals, then 7) free
  14.   the new storage.  The calls to do this are:
  15.  
  16.   1) smooth = initAllTables();
  17.   2) includePolygon(int numVerts, Point3 *verts, Smooth smooth);
  18.   3) (optional) enableEdgePreservation(Smooth smooth, float minDot);
  19.   4) (optional) setFuzzFraction(smooth Smooth, float fuzzFraction);
  20.   5) makeVertexNormals(smooth);
  21.   6) YOUR CODE
  22.   7) freeSmooth();
  23.  
  24.   Edge preservation is used to retain sharp creases in the model.  If it is
  25.   enabled, then the dot product of each pair of polygons sharing a vertex
  26.   is computed.    If this value is below the value of 'minDot' (that is,
  27.   the two polygons are a certain distance away from flatness), then the
  28.   polygons are not averaged together for the vertex normal.
  29.  
  30.   If you want to re-compute the results without edge preservation, call
  31.     disableEdgePreservation(smooth);
  32.  
  33.   The general flow of the algorithm is:
  34.     1. currentHash = scan hashTable
  35.     2. while (any unmarked) {
  36.     3. firstVertex = first unmarked vertex.     set to MARKWORKING
  37.     4. normal = firstVertex->polygon->normal
  38.     5. scan currentHash.  If vertex = firstVertex
  39.         6. normal += vertex->polygon->normal
  40.         7. set vertex to MARKWORKING
  41.         (end of scan)
  42.     8. set normal to unit length
  43.     9. scan currentHash.  If vertex set to MARKWORKING
  44.         10. set vertex->normal = normal
  45.         11. set to MARKDONE
  46.         (end of scan)
  47.     (end while)
  48.  
  49.   The HASH macro must always return a non-negative value, even for negative inputs.
  50.   The size of the hash table can be adjusted to taste.
  51.   The fuzz for comparison needs to be matched to the resolution of the model.
  52. */
  53.  
  54. #include "smooth.h"
  55.  
  56. void     addVertexToTable(Point3 *pt, Polygon polygon, int vNum, Smooth smooth);
  57. void     makePolyNormal(Polygon polygon);
  58. void     writeSmooth(FILE *fp, int numPolys);
  59. HashNode getFirstWaitingNode(HashNode node);
  60. void     processHashNode(HashNode headNode, HashNode firstNode, Smooth smooth);
  61. int     hashPolys(boolean phase);
  62. void     writeGeom(int numPolys);
  63. void     freeSmooth(Smooth smooth);
  64. boolean     compareVerts(Point3 *v0, Point3 *v1, Smooth smooth);
  65. void     computeFuzz(Smooth smooth);
  66.  
  67. /********* ENTRY PROCS *********/
  68.  
  69. /* add this polygon to the tables */
  70. void includePolygon(int numVerts, Point3 *verts, Smooth smooth, void *user) {
  71. int i;
  72. Point3 *vp, *ovp;
  73.     Polygon polygon = NEWTYPE(Polygon_def);
  74.     polygon->next = NULL;
  75.     if (smooth->polyTail != NULL) {
  76.       smooth->polyTail->next = polygon;
  77.     } else {
  78.     smooth->polygonTable = polygon;
  79.     };
  80.     smooth->polyTail = polygon;
  81.     polygon->vertices = NEWA(struct Point3Struct, numVerts);
  82.     polygon->normals = NEWA(struct Point3Struct, numVerts);
  83.     polygon->user = user;
  84.     vp = polygon->vertices;
  85.     ovp = verts;
  86.     polygon->numVerts = numVerts;
  87.  
  88.     for (i=0; i<numVerts; i++) {
  89.     vp->x = ovp->x;
  90.     vp->y = ovp->y;
  91.     vp->z = ovp->z;
  92.     addVertexToTable(vp, polygon, i, smooth);
  93.     vp++;
  94.     ovp++;
  95.     };
  96.     makePolyNormal(polygon);
  97.     }
  98.  
  99. void enableEdgePreservation(Smooth smooth, float minDot) {
  100.     smooth->edgeTest = TRUE;
  101.     smooth->minDot = minDot;
  102.     }
  103.  
  104. void disableEdgePreservation(Smooth smooth) {
  105.     smooth->edgeTest = FALSE;
  106.     }
  107.  
  108. void setFuzzFraction(Smooth smooth, float fuzzFraction) {
  109.     smooth->fuzzFraction = fuzzFraction;
  110.     }
  111.  
  112. /******** PROCEDURES ********/
  113.  
  114. /* set all the hash-table linked lists to NULL */
  115. Smooth initAllTables() {
  116. int i;
  117. Smooth smooth = NEWTYPE(Smooth_def);
  118.     for (i=0; i<HASH_TABLE_SIZE; i++) smooth->hashTable[i] = NULL;
  119.     smooth->polygonTable = NULL;
  120.     smooth->polyTail = NULL;
  121.     smooth->edgeTest = FALSE;
  122.     smooth->minDot = 0.2;
  123.     smooth->fuzzFraction = 0.001;
  124.     smooth->fuzz = 0.001;
  125.     return(smooth);
  126.     }
  127.  
  128. /* hash this vertex and add it into the linked list */
  129. void addVertexToTable(Point3 *pt, Polygon polygon, int vNum, Smooth smooth) {
  130. int hash = HASH(pt);
  131. HashNode newNode = NEWTYPE(HashNode_def);
  132.     newNode->next = smooth->hashTable[hash];
  133.     smooth->hashTable[hash] = newNode;
  134.     newNode->polygon = polygon;
  135.     newNode->vertexNum = vNum;
  136.     newNode->marked = MARKWAITING;
  137.     }
  138.  
  139. /* compute the normal for this polygon using Newell's method */
  140. /* (see Tampieri, Gems III, pg 517) */
  141. void makePolyNormal(Polygon polygon) {
  142. Point3 *vp, *p0, *p1;
  143. int i;
  144.    polygon->normal.x = 0.0; polygon->normal.y = 0.0; polygon->normal.z = 0.0;
  145.    vp = polygon->vertices;
  146.    for (i=0; i<polygon->numVerts; i++) {
  147.       p0 = vp++;
  148.       p1 = vp;
  149.       if (i == polygon->numVerts-1) p1 = polygon->vertices;
  150.       polygon->normal.x += (p1->y - p0->y) * (p1->z + p0->z);
  151.       polygon->normal.y += (p1->z - p0->z) * (p1->x + p0->x);
  152.       polygon->normal.z += (p1->x - p0->x) * (p1->y + p0->y);
  153.       };
  154.    (void) V3Normalize(&(polygon->normal));
  155.    }
  156.  
  157. /* scan each list at each hash table entry until all nodes are marked */
  158. void makeVertexNormals(Smooth smooth) {
  159. HashNode currentHashNode;
  160. HashNode firstNode;
  161. int i;
  162.     computeFuzz(smooth);
  163.     for (i=0; i<HASH_TABLE_SIZE; i++) {
  164.     currentHashNode = smooth->hashTable[i];
  165.     do {
  166.         firstNode = getFirstWaitingNode(currentHashNode);
  167.         if (firstNode != NULL) {
  168.         processHashNode(currentHashNode, firstNode, smooth);
  169.         };
  170.         } while (firstNode != NULL);
  171.     };
  172.     }
  173.  
  174. void computeFuzz(Smooth smooth) {
  175. Point3 min, max;
  176. double od, d;
  177. Point3 *v;
  178. int i;
  179. Polygon poly = smooth->polygonTable;
  180.   min.x = max.x = poly->vertices->x;
  181.   min.y = max.y = poly->vertices->y;
  182.   min.z = max.z = poly->vertices->z;
  183.   while (poly != NULL) {
  184.     v = poly->vertices;
  185.     for (i=0; i<poly->numVerts; i++) {
  186.       if (v->x < min.x) min.x = v->x;
  187.       if (v->y < min.y) min.y = v->y;
  188.       if (v->z < min.z) min.z = v->z;
  189.       if (v->x > max.x) max.x = v->x;
  190.       if (v->y > max.y) max.y = v->y;
  191.       if (v->z > max.z) max.z = v->z;
  192.       v++;
  193.       };
  194.     poly = poly->next;
  195.     };
  196.   d = fabs(max.x - min.x);
  197.   od = fabs(max.y - min.y);  if (od > d) d = od;
  198.   od = fabs(max.z - min.z);  if (od > d) d = od;
  199.   smooth->fuzz = od * smooth->fuzzFraction;
  200.   }
  201.  
  202. /* get first node in this list that isn't marked as done */
  203. HashNode getFirstWaitingNode(HashNode node) {
  204.     while (node != NULL) {
  205.     if (node->marked != MARKDONE) return(node);
  206.     node = node->next;
  207.     };
  208.     return(NULL);
  209.     }
  210.  
  211. /* are these two vertices the same to with the tolerance? */
  212. boolean compareVerts(Point3 *v0, Point3 *v1, Smooth smooth) {
  213.     float q0, q1;
  214.     q0 = QUANT(v0->x); q1 = QUANT(v1->x); if (!FUZZEQ(q0, q1)) return(FALSE);
  215.     q0 = QUANT(v0->y); q1 = QUANT(v1->y); if (!FUZZEQ(q0, q1)) return(FALSE);
  216.     q0 = QUANT(v0->z); q1 = QUANT(v1->z); if (!FUZZEQ(q0, q1)) return(FALSE);
  217.     return(TRUE);
  218.     }
  219.  
  220. /* compute the normal for an unmarked vertex */
  221. void processHashNode(HashNode headNode, HashNode firstNode, Smooth smooth) {
  222.     HashNode scanNode = firstNode->next;
  223.     Point3 *firstVert = &(firstNode->polygon->vertices[firstNode->vertexNum]);
  224.     Point3 *headNorm = &(firstNode->polygon->normal);
  225.     Point3 *testVert, *testNorm;
  226.     Point3 normal;
  227.     float ndot;
  228.  
  229.     firstNode->marked = MARKWORKING;
  230.     normal.x = firstNode->polygon->normal.x;
  231.     normal.y = firstNode->polygon->normal.y;
  232.     normal.z = firstNode->polygon->normal.z;
  233.  
  234.     while (scanNode != NULL) {
  235.     testVert = &(scanNode->polygon->vertices[scanNode->vertexNum]);
  236.     if (compareVerts(testVert, firstVert, smooth)) {
  237.         testNorm = &(scanNode->polygon->normal);
  238.         ndot = V3Dot(testNorm, headNorm);
  239.  
  240.         if ((!(smooth->edgeTest)) || (ndot > smooth->minDot)) {
  241.         V3Add(&normal, testNorm, &normal);
  242.         scanNode->marked = MARKWORKING;
  243.         };
  244.         };
  245.     scanNode = scanNode->next;
  246.     };
  247.  
  248.     V3Normalize(&normal);
  249.  
  250.     scanNode = firstNode;
  251.     while (scanNode != NULL) {
  252.     if (scanNode->marked == MARKWORKING) {
  253.         testNorm = &(scanNode->polygon->normals[scanNode->vertexNum]);
  254.         testNorm->x = normal.x;
  255.         testNorm->y = normal.y;
  256.         testNorm->z = normal.z;
  257.         scanNode->marked = MARKDONE;
  258.         testVert = &(scanNode->polygon->vertices[scanNode->vertexNum]);
  259.         };
  260.     scanNode = scanNode->next;
  261.     };
  262.     }
  263.  
  264. /* free up all the memory */
  265. void freeSmooth(Smooth smooth) {
  266. HashNode headNode;
  267. HashNode nextNode;
  268. Polygon poly;
  269. Polygon nextPoly;
  270. int i;
  271.     for (i=0; i<HASH_TABLE_SIZE; i++) {
  272.     headNode = smooth->hashTable[i];
  273.     while (headNode != NULL) {
  274.         nextNode = headNode->next;
  275.         free(headNode);
  276.         headNode = nextNode;
  277.         };
  278.     };
  279.     poly = smooth->polygonTable;
  280.     while (poly != NULL) {
  281.     nextPoly = poly->next;
  282.     freePoly(poly);
  283.     poly = nextPoly;
  284.     };
  285.     smooth->polygonTable = NULL;
  286.     free(smooth);
  287.     }
  288.  
  289. freePoly(polygon) Polygon polygon; {
  290.     if (polygon->vertices != NULL) free(polygon->vertices);
  291.     if (polygon->normals != NULL) free(polygon->normals);
  292.     polygon->next = NULL;
  293.     free(polygon);
  294.     }
  295.